0423. 从英文中重建数字【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 字母计数

1. 📝 题目描述

• leetcode

给你一个字符串 s，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

---

示例 1：

输入：s = "owoztneoer"
输出："012"

示例 2：

输入：s = "fviefuro"
输出："45"

---

提示：

• 1 <= s.length <= 10^5
• s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
• s 保证是一个符合题目要求的字符串

2. 🎯 s.1 - 字母计数

c

char* originalDigits(char* s) {
    int count[26] = {0};
    for (int i = 0; s[i]; i++) count[s[i] - 'a']++;
    int out[10] = {0};
    out[0] = count['z' - 'a'];
    out[2] = count['w' - 'a'];
    out[4] = count['u' - 'a'];
    out[6] = count['x' - 'a'];
    out[8] = count['g' - 'a'];
    out[3] = count['h' - 'a'] - out[8];
    out[5] = count['f' - 'a'] - out[4];
    out[7] = count['s' - 'a'] - out[6];
    out[1] = count['o' - 'a'] - out[0] - out[2] - out[4];
    out[9] = count['i' - 'a'] - out[5] - out[6] - out[8];
    int total = 0;
    for (int i = 0; i < 10; i++) total += out[i];
    char* res = (char*)malloc(total + 1);
    int idx = 0;
    for (int i = 0; i <= 9; i++)
        for (int j = 0; j < out[i]; j++) res[idx++] = '0' + i;
    res[idx] = '\0';
    return res;
}

js

/**
 * @param {string} s
 * @return {string}
 */
var originalDigits = function (s) {
  const count = new Array(26).fill(0)
  for (const ch of s) count[ch.charCodeAt(0) - 97]++
  const out = new Array(10).fill(0)
  // 唯一字母确定
  out[0] = count['z'.charCodeAt(0) - 97] // zero
  out[2] = count['w'.charCodeAt(0) - 97] // two
  out[4] = count['u'.charCodeAt(0) - 97] // four
  out[6] = count['x'.charCodeAt(0) - 97] // six
  out[8] = count['g'.charCodeAt(0) - 97] // eight
  out[3] = count['h'.charCodeAt(0) - 97] - out[8] // three
  out[5] = count['f'.charCodeAt(0) - 97] - out[4] // five
  out[7] = count['s'.charCodeAt(0) - 97] - out[6] // seven
  out[1] = count['o'.charCodeAt(0) - 97] - out[0] - out[2] - out[4] // one
  out[9] = count['i'.charCodeAt(0) - 97] - out[5] - out[6] - out[8] // nine
  let res = ''
  for (let i = 0; i <= 9; i++) res += String(i).repeat(out[i])
  return res
}

py

class Solution:
    def originalDigits(self, s: str) -> str:
        count = Counter(s)
        out = [0] * 10
        out[0] = count['z']
        out[2] = count['w']
        out[4] = count['u']
        out[6] = count['x']
        out[8] = count['g']
        out[3] = count['h'] - out[8]
        out[5] = count['f'] - out[4]
        out[7] = count['s'] - out[6]
        out[1] = count['o'] - out[0] - out[2] - out[4]
        out[9] = count['i'] - out[5] - out[6] - out[8]
        return ''.join(str(i) * out[i] for i in range(10))

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度
• 空间复杂度：$O(1)$

算法思路：

• 找每个数字单词中的唯一字母：z→0, w→2, u→4, x→6, g→8
• 再用剩余字母推断 3,5,7,1,9